//! # 题目要求：
//! 编写一个程序，找出前两个不能写成一个素数加一个平方的两倍之和的奇合数之和。
//!
//! # 解法：
//! 本题要求找到前两个不能表示为素数与平方两倍之和的奇合数。本题目要求处理数据量较小，故采用穷举法进行求解。 
//! 使用穷举法从 9 开始遍历所有奇数，并判断其是否可以表示为一个素数 `p` 加上一个平方的两倍，即 `n = p + 2 * k^2`。
//! 如果 `n` 无法表示为这种形式，即满足题意条件，则将其计入结果。
//! 遍历直到找到前两个符合条件的奇合数，求它们的和并返回。
//! 
//! # 正确性与性能评估：
//! 本程序成功找到了前两个不能表示为素数与平方两倍之和的奇合数，并计算出其和。通过了以下几个方面的评估：
//!
//! ## 正确性验证：
//! - 程序通过了题目要求的测试用例，返回了正确的结果。
//! - 在 **181.878695 毫秒** 内完成了计算，远小于题目规定的时间限制（500 毫秒），证明算法正确且高效。
//!
//! ## 性能评估：
//! - **运行时间**：
//!   程序在 **181.878695 毫秒** 内完成，符合题目规定的 **500 毫秒** 的时间限制。
//! 
//! - **时间复杂度**：
//!   对于每个奇数 `n`，我们需要遍历小于 `n` 的所有素数并检查它们与平方两倍之和的关系，
//!   具体来说，对于每个奇数 `n`，最坏情况下需要检查 `n` 个素数。检查每个素数时需要计算它是否能与平方数之和匹配，
//!   其中计算平方数的时间复杂度为 O(√n)。因此，整体的时间复杂度为 O(n * √n)，由于 `n` 范围较小，该复杂度是可以接受的。
//!
//! - **空间复杂度**：
//!   本题没有使用任何额外的数据结构（如数组或哈希集），空间复杂度是常数级别的 O(1)。
//!

/// 找出前两个不能被表示为素数与平方两倍之和的奇合数，并返回它们的和。
///
/// # 返回值
/// - `u64`: 前两个满足条件的奇合数之和。
pub fn goldbach_conjecture() -> u64 {
    // 使用迭代器实现奇合数的生成和过滤
    (9..)// 从 9 开始生成无限序列,仅保留奇数，跳过偶数
        .step_by(2) 
        .filter(|&n| !is_prime(n) && !can_be_expressed(n)) // 筛选不能表示为素数和平方两倍之和的数
        .take(2)
        .sum()
}

/// 检查输入参数n是否是素数
/// 
/// # 参数
/// - `n`: 要判断的正整数
/// 
/// # 返回
/// - 如果是素数则返回 `true`，否则返回 `false`
fn is_prime(n: u64) -> bool {
    match n {
        0 | 1 => false, // 0 和 1 不是素数
        2 => true, // 2 是素数
        _ if n % 2 == 0 => false, // 偶数（除了 2）都不是素数
        _ => !(3..=(n as f64).sqrt() as u64)// 遍历从 3 到 sqrt(n) 的所有奇数
            .step_by(2)
            .any(|i| n % i == 0),// 如果找到任何可以整除 n 的数，则 n 不是素数
    }
}

/// 检查一个奇合数是否可以表示为一个素数加上一个平方的两倍
/// 
/// # 参数
/// - `n`: 奇合数
/// 
/// # 返回
/// - 如果可以表示则返回 `true`，否则返回 `false`
fn can_be_expressed(n: u64) -> bool {
    (2..n)// 遍历小于 n 的所有数
        .filter(|&p| is_prime(p))// 对这些数进行筛选,只保留素数
        .any(|p| {
            //检查给定的奇合数 n 是否可以表示为一个素数 p 加上一个平方的两倍
            // 即是否存在一个素数 p 和一个整数 k 使得 n = p + 2 * k^2
            let remainder = n - p;
            remainder % 2 == 0 && {
                let half_remainder = remainder / 2;
                let sqrt = (half_remainder as f64).sqrt() as u64;
                sqrt * sqrt == half_remainder
            }
        })
}